//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和
//。假定每组输入只存在唯一答案。 
//
// 
//
// 示例： 
//
// 输入：nums = [-1,2,1,-4], target = 1
//输出：2
//解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
// 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 10^3 
// -10^3 <= nums[i] <= 10^3 
// -10^4 <= target <= 10^4 
// 
// Related Topics 数组 双指针 
// 👍 542 👎 0

package leetcode.editor.cn;

import java.util.Arrays;

//Java：最接近的三数之和
public class P16ThreeSumClosest {

    /**
     * 思路: 就直接将第15题的代码复制过来，修改一下判断的方法就行了
     *
     * 执行用时： 8 ms , 在所有 Java 提交中击败了 31.55% 的用户 内存消耗： 39.5 MB , 在所有 Java 提交中击败了 32.66% 的用户
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int threeSumClosest(int[] nums, int target) {
            Integer result = null;
            Arrays.sort(nums);

            for (int i = 0; i < nums.length - 2; i++) {
                // i 和前一位一样，就不用算了
                if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
                    continue;
                }

                int j = i + 1;
                int k = nums.length - 1;

                // [-4,-1,1,2]
                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (result == null || Math.abs(sum - target) < Math.abs(result - target)) {
                        result = sum;
                    }
                    if (sum > target) {
                        k--;
                    } else if (sum < target) {
                        j++;
                    } else {
                        return sum;
                    }
                }
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P16ThreeSumClosest().new Solution();
        int[] nums = new int[]{-1, 2, 3};
        System.out.println(solution.threeSumClosest(nums, 1));
        // TO TEST
    }

}